package code2201_2300.code20_30;

import java.awt.*;

/**
 * 统计一个数字在排序数组中出现的次数
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 */
public class _2212search {

    /**
     * 初始直接便利数组，效率极低
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 26.62%     * 的用户
     * 内存消耗：     * 41.4 MB     * , 在所有 Java 提交中击败了     * 79.83%     * 的用户
     *
     * 评论区热评：面试官出这题的话肯定是想让你写二分的啦 其他没用（自己忽视了是排序数组的前提条件）
     * 此处是一个二分法贼经典的题，值得收藏！
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 41.2 MB     * , 在所有 Java 提交中击败了     * 72.49%     * 的用户
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums,int target){
        if(nums.length==0)return 0;
        int findLeftNum = findLeftNum(nums,target);
        if(findLeftNum==-1)return 0;
        // 找左边的要向下取整，找右边的要向上取整
        int findRightNum = findRightNum(nums,target);
        return findRightNum-findLeftNum+1;
    }

    private static int findRightNum(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int mid;
        while (left < right){
            mid = left+(right-left+1)/2;
            if(nums[mid]>target){
                right = mid - 1;
            }else if(nums[mid]<target){
                left = mid + 1;
            }else {
                left = mid;
            }
        }
        return left;
    }

    private static int findLeftNum(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int mid;
        while (left<right){
            mid = left+(right-left)/2;
            if(nums[mid]>target){
                right = mid - 1;
            }else if(nums[mid]<target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        if(nums[left]!=target)return -1;
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
        System.out.println(search(nums,8));
    }
}
